package com.cet.algorithm.双指针法;

/**
 * @program: algorithm
 * @description: 颠倒字符串里面的单词
 * @author: 陈恩涛
 * @create: 2022-03-24 11:28
 **/
public class ReverseWords {
    /**
     * 解题思路：
     * 1、移除多余的空格
     * 2、反转整个字符串
     * 3、将其中每个单词颠倒
     * 例如："  I can  control myself   "
     * ----> "I can control myself"
     * ----> "flesym lortnoc nac I"
     * ----> "myself control can I"
     */

    /**
     * 移除多余的空格
     * @param s
     * @return
     */
    private String removeExtraSpace(String s) {
        StringBuilder result = new StringBuilder();
        int left = 0;
        int right = s.length() - 1;
        while (s.charAt(left) == ' ') {
            left++;
        }
        while (s.charAt(right) == ' ') {
            right--;
        }
        for (int i = left; i <= right; i++) {
            if(s.charAt(i) != ' ' || result.charAt(result.length() - 1) != ' ') {
                result.append(s.charAt(i));
            }
        }
        return result.toString();
    }

    /**
     * 颠倒字符串
     * @param s
     * @param start
     * @param end
     * @return
     */
    private String reverseString(String s, int start, int end) {
        StringBuilder result = new StringBuilder(s);
        while (start < end) {
            char temp = result.charAt(start);
            result.setCharAt(start,result.charAt(end));
            result.setCharAt(end, temp);
            start++;
            end--;
        }
        return result.toString();
    }

    private String reverseEachWord(String s) {
        // 加个哨兵位，便于循环
        s += " ";
        StringBuilder result = new StringBuilder();
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < s.length(); fastIndex++) {
            if (s.charAt(fastIndex) == ' ') {
                result.append(reverseString(s.substring(slowIndex, fastIndex), 0, fastIndex - slowIndex - 1)).append(" ");
                slowIndex = fastIndex + 1;
            }
        }
        return result.toString().substring(0, result.length() - 1);
    }


    public static void main(String[] args) {
        ReverseWords rw = new ReverseWords();
        String s2 = rw.removeExtraSpace("  abc ded  g ");
        String s3 = rw.reverseString(s2, 0, s2.length() - 1);
        String s4 = rw.reverseEachWord(s3);
        System.out.println(s4);
    }
}
